本篇同步發布於Blog: [解題] POJ - 1182 食物链

平台：

PKU Online Judge

題號：

1182 - 食物链

題目連結：

http://poj.org/problem?id=1182

題目說明：

　　這題是中文題目，可以看原文的敘述。這裡再簡化敘述，有從1...N的N個編號物種，每個物種可能歸類在A、B、C其中一種，A會吃B、B會吃C、C會吃A。

　　接著有K筆敘述，每一筆有D、X、Y，D等於1時是X和Y同物種，D等於2時是X會吃Y。

　　但這K筆敘述不完全是對的，要找出後面敘述與前面敘述矛盾的筆數。比如前面第1筆敘述1和2同物種，但之後第2筆敘述說2能吃1，這樣是矛盾的。除了矛盾之外，也要檢查物種編號是否在1...N之間，否則也要歸類矛盾的筆數。

範例輸入：

100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5

範例輸出：

3

解題方法：

　　這題可用Union and Find，將物種與食物鏈都用同一種分組的方式。由於有分A、B、C三個物種，於是用偏移量 N 與 2*N 代表 B與C。

　　一開始先初始化，每個物種都只屬於自己的編號，尚未與別人做分組。

　　每一筆敘述，如果X與Y是同一種，同時建立X-A與Y-A、X-B與Y-B、X-C與Y-C的群組，但建立這群組前要先檢查是否X-A與Y-B的群組已存在或者X-A與Y-C的群組已存在，否則這X與Y是同一種的敘述是矛盾的。

　　如果X與Y是X吃Y，同時建立X-A與Y-B、X-B與Y-C、X-C與Y-A的群組，但建立這群組前要先檢查是否X-A與Y-A的群組已存在或者X-A與Y-C的群組已存在，否則這X吃Y的敘述是矛盾的。

　　以範例輸入來看：

1. 第1筆敘述，X = 101這物種編號超過N，屬於矛盾
2. 第2筆敘述，X = 1 能吃 Y = 2，因此建立 (1, 2 + 100), (1 + 100, 2 + 200), ( 1 + 200, 2) 三種群組，代表食物鏈
3. 第3筆敘述，X = 2 能吃 Y = 3，因此建立(2, 3 + 100), (2 + 100, 3 + 200), ( 2 + 200, 3) 三種群組，代表食物鏈
4. 第4筆敘述，X = 3 能吃 Y = 3，產生了自己就是屬於同物種的矛盾
5. 第5筆敘述，X = 1 和 Y = 3 同物種，但X = 1所屬群組 等於 Y = 3的群組(3 + 200的食物鏈包含在2 + 100, 2 + 100 又包含在 1) 相同，食物鏈產生矛盾
6. 第6筆敘述，X = 3 能吃 Y = 1，因此建立(3, 1 + 100), (3 + 100, 1 + 200), ( 3 + 200, 1) 三種群組，代表食物鏈
7. 第7筆敘述，X = 5 和 Y = 5同物種，都在同一個群組，屬於正確的敘述

　　所以一共有3筆敘述是矛盾的，回傳3。　　

　　題目輸入有些陷阱，比如資料量過大，要用scanf()而不是cin，否則會超時；另外不要用while()讀測資，只要讀一次就好，否則會WA。。。

難度為Medium

程式碼：

#include <iostream>
#include <cstdio>
#define MAXN 150005

using namespace std;

int ranks[MAXN];
int pre[MAXN];

void init(int n)
{
    for(int i = 0 ; i < n; ++i)
    {
        pre[i] = i;
        ranks[i] = 0;
    }
}

int findl(int x)
{
    if(pre[x] == x)
    {
        return x;
    }
    else
    {
        return pre[x] = findl(pre[x]);
    }
}

void unite(int x, int y)
{
    x = findl(x);
    y = findl(y);

    if(x == y)
    {
        return;
    }

    if(ranks[x] < ranks[y])
    {
        pre[x] = y;
    }
    else
    {
        pre[y] = x;
        if(ranks[x] == ranks[y])
        {
            ranks[x]++;
        }
    }
}

bool same(int x, int y)
{
    return findl(x) == findl(y);
}

int main()
{
    int N, K;
    int D, X, Y;
    scanf("%d %d", &N, &K);
    int ans = 0;
    init(N * 3);
    for(int i = 0 ; i < K; ++i)
    {
        scanf("%d %d %d", &D, &X, &Y);
        X = X - 1;
        Y = Y - 1;

        if(X < 0 || X >= N || Y < 0 || Y >= N)
        {
            ans++;
            continue;
        }

        if(D == 1)
        {
            if(same(X, Y + N) || same(X, Y + 2 * N))
            {
                ans++;
            }
            else
            {
                unite(X, Y);
                unite(X + N, Y + N);
                unite(X + 2 * N, Y + 2 * N);
            }
        }
        else if(D == 2)
        {
            if(same(X, Y) || same(X, Y + 2 * N))
            {
                ans++;
            }
            else
            {
                unite(X, Y + N);
                unite(X + N, Y + N * 2);
                unite(X + 2 * N, Y);
            }
        }
    }

    printf("%d\n", ans);
    return 0;
}

GITHUB位置：

https://github.com/u8989332/ProblemSolving/blob/master/PKUOnlineJudge/1100-1199/1182.cpp